package com.zj.leetcode.medium.stack;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;

/**
 * @program: algorithm
 * @description: 基本计算器 II
 * 227 basic-calculator-ii
 * <p>
 * 给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。
 * <p>
 * 整数除法仅保留整数部分。
 * <p>
 *  
 * <p>
 * 示例 1：
 * <p>
 * 输入：s = "3+2*2"
 * 输出：7
 * 示例 2：
 * <p>
 * 输入：s = " 3/2 "
 * 输出：1
 * 示例 3：
 * <p>
 * 输入：s = " 3+5 / 2 "
 * 输出：5
 *  
 * 提示：
 * 1 <= s.length <= 3 * 105
 * s 由整数和算符 ('+', '-', '*', '/') 组成，中间由一些空格隔开
 * s 表示一个 有效表达式
 * 表达式中的所有整数都是非负整数，且在范围 [0, 231 - 1] 内
 * 题目数据保证答案是一个 32-bit 整数
 * @author: Zhang Bo
 * @create: 2022-01-14 17:05
 **/
public class BasicCalculatorIi {
    public static void main(String[] args) {
//        String s = " 3+5 / 2 ";
        String s = "3+2*2";
//        String s = " 3/2 ";
//        String s = " 32/2 ";
//        String s = "1-1+1";
//        String s = "89";
        Solution solution = new BasicCalculatorIi().new Solution();
        System.out.println(solution.calculate02(s));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int calculate(String s) {

//            Stack<Integer> nums = new Stack<>();
//            Stack<Character> symbols = new Stack<>();
            Deque<Integer> nums = new ArrayDeque<>();
            Deque<Character> symbols = new ArrayDeque<>();
            int left = 0;
            int right = 0;
            while (right < s.length()) {

                if (s.charAt(right) < 48 || s.charAt(right) > 57) {
                    if (s.charAt(right) != ' ') {
                        symbols.addLast(s.charAt(right));
                    }
                }
                right++;

                if (s.charAt(left) < 48 || s.charAt(left) > 57) {
                    left++;
                } else if (right == s.length() || (s.charAt(right) < 48 || s.charAt(right) > 57)) {
                    int item = Integer.parseInt(s.substring(left, right));

                    if (!symbols.isEmpty()) {
                        Character peek = symbols.peekLast();
                        if (peek == '/') {
                            symbols.pollLast();
                            Integer num = nums.pollLast();
                            nums.addLast(num / item);
                        } else if (peek == '*') {
                            symbols.pollLast();
                            Integer num = nums.pollLast();
                            nums.addLast(num * item);
                        } else {
                            nums.addLast(item);
                        }
                    } else {
                        nums.addLast(item);
                    }


                    left = right;
                }


            }

            while (!symbols.isEmpty()) {
                Integer one = nums.pollFirst();
                Integer two = nums.pollFirst();
                Character sym = symbols.pollFirst();
                if (sym == '+') {
                    nums.addFirst(one + two);
                } else if (sym == '-') {
                    nums.addFirst(one - two);
                }
            }
            return nums.isEmpty() ? 0 : nums.pollFirst();
        }


        /**
         * 1）其实减法也可以提前处理，
         * 当成负数就好了
         * 2）对于如何判断下一个是否为数字，这里也给出了很好的设计，
         * 只要为数字就加到临时变量中，如果下一个不是数字，临时变量重置，很巧妙哦
         * @param s
         * @return
         */
        public int calculate02(String s) {
            Deque<Integer> stack = new LinkedList<Integer>();
            char preSign = '+';
            int num = 0;
            int n = s.length();
            for (int i = 0; i < n; ++i) {
                if (Character.isDigit(s.charAt(i))) {
                    num = num * 10 + s.charAt(i) - '0';
                }
                if (!Character.isDigit(s.charAt(i)) && s.charAt(i) != ' ' || i == n - 1) {
                    switch (preSign) {
                        case '+':
                            stack.push(num);
                            break;
                        case '-':
                            stack.push(-num);
                            break;
                        case '*':
                            stack.push(stack.pop() * num);
                            break;
                        default:
                            stack.push(stack.pop() / num);
                    }
                    preSign = s.charAt(i);
                    num = 0;
                }
            }
            int ans = 0;
            while (!stack.isEmpty()) {
                ans += stack.pop();
            }
            return ans;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
